#pragma once
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <stdexcept>
#include <memory>
#include<climits>


struct edge{
   int from;
   int to;
   edge(int from, int to) : from(from), to(to) {}
   bool operator < (const edge tmp) const{
       if(from < tmp.from) return true;
       if(from == tmp.from) return (to < tmp.to);
       return false;
   }
   bool operator == (const edge tmp)const{
       return(from == tmp.from && to == tmp.to);
   }
   edge(){}
};

class Graph{
private:

public:
   virtual int GetNumberOfVertices() const = 0;
   virtual std::set < int > GetIncidentList(const int vertex)const = 0;
   virtual ~Graph() {};
};

struct ConnectivityMatrix : public Graph{
private:
   std::vector < std::vector < bool > > Matrix;
   int vertices_number;
    
public:
   
   int GetNumberOfVertices()const{ return vertices_number;}
   
   
   ConnectivityMatrix(const int vertices_nmbr, const std::vector < edge > &edges){
       vertices_number = vertices_nmbr;
       Matrix.resize(vertices_number, std::vector<bool>(vertices_number, false));
       for(int  i = 0; i < edges.size(); i++){
           edge current_edge = edges[i];
           Matrix[current_edge.from][current_edge.to] = true;
       }
   }
   
   virtual std::set < int > GetIncidentList(const int vertex)const{
       std::set <int > result;
       for(int current_vertex = 0; current_vertex < vertices_number; current_vertex++){
           if(Matrix[vertex][current_vertex]) {
               result.insert(current_vertex);
           }
       }
       return result;
   }
};
   




struct ConnectivityList : public Graph{
private:
   std:: vector < int > beginnings;
    std::vector < int > ends_of_edges;
    int vertices_number;
    int edges_number;
public:
    
    int GetNumberOfVertices()const{ return vertices_number;}
    
    
    ConnectivityList(const int vertices_nmbr, const std::vector < edge > &edges){
        vertices_number = vertices_nmbr;
        edges_number = edges.size();
        beginnings.resize(vertices_number, 0);
        for(int i = 0; i < edges.size(); i++){
            edge current_edge = edges[i];
            ends_of_edges.insert(ends_of_edges.begin() + beginnings[current_edge.from], current_edge.to);
            for(int j = current_edge.from + 1; j < vertices_number; j++){
                beginnings[j]++;
            }
        }
        
    }
    
    std::set < int > GetIncidentList(const int vertex)const{
        std::vector < int >::const_iterator begin = ends_of_edges.begin() + beginnings[vertex];
        std::vector < int > ::const_iterator end;
        if ( vertex == vertices_number - 1){
            end = ends_of_edges.end();
        }
        else {
            end = ends_of_edges.begin() + beginnings[vertex + 1];
        }
        std::vector <int> vector_result;
        vector_result.assign(begin, end);
        std::set<int> result(vector_result.begin(), vector_result.end());
        return result;
    }
    
  
    
  
     ~ConnectivityList() {}
};	

inline std::auto_ptr<Graph> MakeCompactGraph(int number_of_vertices, std::vector <edge> &edges){
    int number_of_edges = edges.size();
    if(number_of_vertices * number_of_vertices * sizeof(bool) / CHAR_BIT> (number_of_vertices + number_of_edges) * sizeof(int)){
       return std::auto_ptr<Graph>(new ConnectivityList(number_of_vertices, edges));
    }
    else {
        return std::auto_ptr<Graph>( new ConnectivityMatrix(number_of_vertices, edges));
    }
}


